package com.squirrel.michale;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/6 4:05 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0100 {

    // 深度优先遍历  deep search first traversal
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null) {
            if (p.val == q.val&&isSameTree(p.left,q.left)&&isSameTree(p.right,q.right)) {
                return true;
            }
        }
        return false;
    }


    // 深度优先遍历  deep search first traversal

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null) {
            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();
            HashSet<TreeNode> setP = new HashSet<>();
            HashSet<TreeNode> setQ = new HashSet<>();

            stackP.add(p);
            stackQ.add(q);
            setP.add(p);
            setQ.add(q);

            while (!stackP.isEmpty()) {
                while (!stackQ.isEmpty()) {
                    TreeNode pNode = stackP.pop();
                    setP.add(pNode);
                    TreeNode qNode = stackQ.pop();
                    setQ.add(qNode);
                    if (pNode != null && qNode != null) {
                        if (pNode.val != qNode.val) {
                            return false;
                        }
                        TreeNode pLeft = pNode.left;
                        TreeNode qLeft = qNode.left;
                        if (pLeft == null && qLeft != null) {
                            return false;
                        }
                        if (pLeft != null && qLeft == null) {
                            return false;
                        }
                        if (pLeft != null && qLeft != null) {
                            if (!setP.contains(pLeft)) {
                                stackP.push(pLeft);
                                setP.add(pLeft);
                            }

                            if (!setQ.contains(qLeft)) {
                                stackQ.push(qLeft);
                                setQ.add(qLeft);
                            }
                        }

                        TreeNode pRight = pNode.right;
                        TreeNode qRight = qNode.right;
                        if (pRight == null && qRight != null) {
                            return false;
                        }
                        if (pRight != null && qRight == null) {
                            return false;
                        }
                        if (pRight != null && qRight != null) {
                            if (!setP.contains(pRight)) {
                                stackP.push(pRight);
                                setP.add(pRight);
                            }

                            if (!setQ.contains(qRight)) {
                                stackQ.push(qRight);
                                setQ.add(qRight);
                            }
                        }
                    }
                    if (pNode != null && qNode == null) {
                        return false;
                    }
                    if (pNode == null && qNode != null) {
                        return false;
                    }
                }
            }
            return true;
        }
        return false;
    }


    public boolean isSameTree3(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p != null && q != null) {
            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();
            HashSet<TreeNode> setP = new HashSet<>();
            HashSet<TreeNode> setQ = new HashSet<>();

            stackP.add(p);
            stackQ.add(q);
            setP.add(p);
            setQ.add(q);

            while (!stackP.isEmpty()) {
                while (!stackQ.isEmpty()) {
                    TreeNode pNode = stackP.pop();
                    setP.add(pNode);
                    TreeNode qNode = stackQ.pop();
                    setQ.add(qNode);
                    if (pNode != null && qNode != null) {
                        if (pNode.val != qNode.val) {
                            return false;
                        }
                        TreeNode pLeft = pNode.left;
                        TreeNode qLeft = qNode.left;
                        if (pLeft == null && qLeft != null) {
                            return false;
                        }
                        if (pLeft != null && qLeft == null) {
                            return false;
                        }
                        if (pLeft != null && qLeft != null) {
                            if (!setP.contains(pLeft)) {
                                stackP.push(pLeft);
                                setP.add(pLeft);
                            }

                            if (!setQ.contains(qLeft)) {
                                stackQ.push(qLeft);
                                setQ.add(qLeft);
                            }
                        }

                        TreeNode pRight = pNode.right;
                        TreeNode qRight = qNode.right;
                        if (pRight == null && qRight != null) {
                            return false;
                        }
                        if (pRight != null && qRight == null) {
                            return false;
                        }
                        if (pRight != null && qRight != null) {
                            if (!setP.contains(pRight)) {
                                stackP.push(pRight);
                                setP.add(pRight);
                            }

                            if (!setQ.contains(qRight)) {
                                stackQ.push(qRight);
                                setQ.add(qRight);
                            }
                        }
                    }
                    if (pNode != null && qNode == null) {
                        return false;
                    }
                    if (pNode == null && qNode != null) {
                        return false;
                    }
                }
            }
            return true;
        }
        return false;
    }

    // 广度优先遍历  breath search first traversal

    public boolean isSameTree4(TreeNode p, TreeNode q) {

        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        Queue<TreeNode> pQueue = new LinkedList<>();
        Queue<TreeNode> qQueue = new LinkedList<>();

        pQueue.offer(p);
        qQueue.offer(q);

        while (!pQueue.isEmpty() && !qQueue.isEmpty()) {

            TreeNode pNode = pQueue.poll();
            TreeNode qNode = qQueue.poll();

            if (pNode.val != qNode.val) {
                return false;
            }

            TreeNode pLeft = pNode.left;
            TreeNode qLeft = qNode.left;
            TreeNode pRight = pNode.right;
            TreeNode qRight = qNode.right;




        }

        return false;
    }


    public static void main(String[] args) {

        LeetCode0100 leetCode0100 = new LeetCode0100();

        TreeNode p = new TreeNode(1, new TreeNode(2, null,null), null);
        TreeNode q = new TreeNode(1, null,new TreeNode(2, null,null));
//        System.out.println(leetCode0100.isSameTree(p, q));
//        System.out.println(leetCode0100.isSameTree2(p, q));


        TreeNode p1 = new TreeNode(1, new TreeNode(2, null,null), new TreeNode(3, null,null));
        TreeNode q1 = new TreeNode(1, new TreeNode(2, null,null), new TreeNode(3, null,null));
//        System.out.println(leetCode0100.isSameTree2(p1, q1));
//        System.out.println(leetCode0100.isSameTree2(p1, q1));


        TreeNode p2 = new TreeNode(2, null, new TreeNode(4, null,null));
        TreeNode q2 = new TreeNode(2, new TreeNode(3, null,null), new TreeNode(4, null,null));
//        System.out.println(leetCode0100.isSameTree2(p1, q1));
        System.out.println(leetCode0100.isSameTree2(p2, q2));
    }
}
